package _14_滑动窗口;

public class _713_乘积小于K的子数组 {

    public static void main(String[] args) {
        _713_乘积小于K的子数组 v = new _713_乘积小于K的子数组();
        int[] ins = new int[]{10, 5, 2, 6};
        System.out.println(v.numSubarrayProductLessThanK(ins, 100));
    }

    // 双指针查找
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        // 右指针一直移动
        int left = 0;
        int total = 1;
        int ans = 0;
        for (int right = 0; right < nums.length; right++) {
            total *= nums[right];
            // 查看是否超过指定的值
            while (total >= k) total /= nums[left++];
            ans += right - left + 1; // 关键理解这一句
        }
        return ans;
    }

    // O(n^2) 遍历查找
    public int numSubarrayProductLessThanK1(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int total = 1;
            for (int j = i; j < nums.length; j++) {
                if ((total *= nums[j]) >= k) break;
                count++;
            }
        }
        return count;
    }

}
